\section{解二次同余式}

\begin{frame}{解二次同余式}
  \color{gray}
考虑二次同余式的具体求解方法（不用上一章讲的借助原根和指标这种方法，也不是逐个尝试）。 先考虑
\[
x^{2} \equiv a \quad\left(\mod  p\right)
\]
($p$ 为奇素数). 可以用二次互反律等方法判断其是否有解。 现设其有解， 即
\[
(a / p)=1,
\]
要考虑求解的具体方法。

~

(I) 若 $p=4n+3$. 由 $(a / p)=1$ 知 $a^{2n+1}=a^{\frac{p-1}{2}} \equiv 1\left(\mod  p\right)$, 故
\[
  \begin{aligned}
    a^{2n+2} \equiv a \quad\left(\mod  p\right), \quad\text{从而}\quad
  \left(a^{n+1}\right)^{2} \equiv a \quad\left(\mod  p\right).
\end{aligned}
\]
故同余式 $x^{2} \equiv a\left(\mod  p\right)$ 的解为$x \equiv \pm a^{n+1}$.

\begin{example}
  \color{gray}
  求解$x^2\equiv 21\left( \mod 43 \right)$. 可算得$(21/43)=1$. 因此所给同余式有解，
    \[
      x\equiv \pm 21^{11} \equiv \mp 8\left( \mod 43 \right).
    \]
\end{example}

\end{frame}

\begin{frame}
  \color{gray}
  (II) 若 $p=8n+5$. 由 $a^{4n+2}=a^{\frac{p-1}{2}} \equiv 1\left(\mod  p\right)$, 可得
\[
\begin{aligned}
  a^{2n+1} \equiv \pm 1 \left(\mod  p\right),\quad \text{从而}\quad
  (a^{n+1})^{2} = a^{2n+2} \equiv \pm a \left(\mod  p\right).
\end{aligned}
\]
正号情形已得解，两个解为$x\equiv \pm a^{n+1}\left( \mod p \right)$;
在负号情形，注意到$-1$有平方根$2^{2n+1}$.
诚然，我们有%
\footnote{对任一个非二次剩余$b$都有$b^{2n+1}$是$-1$的平方根。
另外，由于$p\equiv 1\left( \mod 4 \right)$, \S4.1引理2(2)表明$(\frac{p-1}{2})!$是$-1$的平方根。
当然，$-1\left( \mod p \right)$的平方根至多两个，这些无非相差个符号。}
  \[
  -1\equiv \kronecker{2}{p} \equiv 2^{\frac{p-1}{2}}\equiv 2^{4n+2}=(2^{2n+1})^2 \left( \mod p \right).
\]
从而
\[
  (2^{2n+1} a^{n+1}  )^{2} \equiv a \quad\left(\mod  p\right),
\]
也可得 $x^{2} \equiv a\left(\mod  p\right)$的两个解为
\[
  x\equiv \pm 2^{2n+1} a^{n+1} \left( \mod p \right).
\]

\begin{example}
  \color{gray}
  求解$x^2\equiv 5\left( \mod 29 \right)$. 可计算得$(5/29)=1$,
  故有解。
  故$5^{14}\equiv 1\left( \mod 29 \right)$. 又计算得$5^7\equiv -1\left( \mod 29 \right)$, $(5^4)^2\equiv -5\left( \mod 29 \right)$,
    故$x^2\equiv 5\left( \mod 29 \right)$的两个解为
  \[
    x\equiv \pm 5^4\cdot 2^7\equiv \pm 18\left( \mod 29 \right).
  \]
%  \footnote{
%    除了直接计算$\frac{p-1}{2}!$得到$-1$的一个平方根，也可如下找到一个平方根。
%    一方面，在$S=\{2,\cdots,\frac{p-1}{2}\}$中可找到$-1$的一个平方根。
%    诚然，若$g\in S$非$-1$的平方根，则可找到$g\neq g'\in S$使得$gg'\equiv \pm 1\left( \mod p \right)$. 
%    不断地去掉这样的一对数$g, g'$, 最终剩下$-1$的平方根。$p=29$时$S$中所有的这样的一对数有：
%    $2, 14$; $3,10$; $4, 7$; $5,6$; $8, 11$; $9, 13$. 故$12$为$-1$的平方根。
%    另一方面，
%    注意到$-1\equiv 28=2^2\cdot 7\left( \mod 29 \right)$, 只用找$7$的平方根。
%    容易观察到$6^2\equiv 7\left( \mod 29 \right)$. 
%    故$-1\left( \mod 29 \right)$的一个平方根为$12$,
%    可用$12$替代$14!$.
%    而且必有$14!\equiv \pm 12\left( \mod 29 \right)$.
%  }
\end{example}
\end{frame}

\begin{frame}
  \color{gray}
(III) 若 $p =8n+1$. 还没有明确的解的公式， 对不太大的 $p$ 可用逐步排除法： 解 $x^{2} \equiv a\left(\mod  p\right)$ 相当于解不定方程
\[
x^{2}=a+p y,
\]
可设 $0<a<p, 0<x<p / 2$, 从而知 $0<y<p / 4$ (限制了 $y$ 的取值范围). 我们目的是求 $y$ 的值使 $a+p y$ 为平方数。 现任取 $c>2$ 与 $p$ 互素， 求模 $c$ 的二次非剩余 $n_{1}$, $n_{2}, \cdots$ (任意多个), 并求 $a+p y_{1} \equiv n_{1}\left(\mod  c\right), a+p y_{2} \equiv n_{2}\left(\mod  c\right), \cdots$ 的解 $y_{1}$, $y_{2}, \cdots$. 则可将 $\left\{y_{1}, y_{2}, \cdots\right\}$ 排除在 $y$ 的取值之外一一因为 $y$ 取这些值时， $a+$ $p y$ 为模 $c$ 非剩余， 就不可能是平方数。 这就排除了 $y$ 的一批可能取值。 再取不同的 $c$ 进一步排除，最后可得到解。

\begin{example}%例1
  \color{gray}
求解
\(
  x^{2} \equiv 79 \left(\mod  241\right).
\)
由 $(79 / 241)=(241 / 79)=(4 / 79)=1$, 知有解。 现欲解 $x^{2}=79+241 y$, 而 $y<241 / 4< 61$. 取 $c=3$, 模 $3$ 的二次非剩余有 $n_{1}=-1$, 而 $79+241 y \equiv-1\left(\mod  3\right)$ 的解为 $y \equiv$ $1\left(\mod  3\right)$, 此种 $y$ 可排除。 又取 $c=5$, 得 $n_{i}= \pm 2$, 而 $79+241 y \equiv \pm 2\left(\mod  5\right)$ 的解为 $y \equiv 3,4\left(\mod  5\right)$, 均排除。 再取 $c=7$, 得 $n_{i}= \pm 2,-1$, 而 $79+241 y \equiv \pm 2$, $-1\left(\mod  7\right)$ 的解为 $y \equiv \pm 1,5\left(\mod  7\right)$, 均排除。 然后取 $c=11$, 得 $n_{i}=2,6,7, 8,10$, 而 $79+241 y \equiv n_{i}\left(\mod  11\right)$ 的解为 $y \equiv 0,3,5,6,7\left(\mod  11\right)$, 均排除。可以继续排除，也可直接验证，得
\[
  y=42, \quad x^{2}=79+241 y=10201.
\]
故解得 $x \equiv \pm 101\left(\mod  241\right)$.
\end{example}
\end{frame}

\begin{frame}
  \color{gray}
现在考虑一般情形。一般的二次同余式可以写为
\begin{equation*}
a x^{2}+b x+c \equiv 0 \quad\left(\mod  m\right), \quad a \nequiv 0 \quad\left(\mod  m\right) \tag{1}
\end{equation*}
将 $m$ 因子分解， 则此同余式归结为模素数幂 $p^{s}$ 的同余式 (见 83.5 引理 1):
\begin{equation*}
a x^{2}+b x+c \equiv 0 \quad\left(\mod  p^{s}\right) \tag{2}
\end{equation*}
这在一定条件下可归结为模素数 $p$ 的同余式
\begin{equation*}
a x^{2}+b x+c \equiv 0 \quad\left(\mod  p\right) \tag{3}
\end{equation*}
事实上， (2) 的解也是 (3) 的解; 且当 $f(x) \equiv f^{\prime}(x) \equiv 0\left(\mod  p\right)$ 无公共解时， (3) 的解可提升为 (2) 的解 (这里 $f(x)=a x^{2}+b x+c \equiv 0$. 见 \S3.5 定理 4 和习题 8).

若 $p^{s} \mid(a, b, c)$, (2) 式自然有解。 否则设 $p^{e} \|(a, b, c), e<s$, 则从系数和 $p^{s}$ 中消去 $p^{e}$ 后， 得到形如 (2) 的方程， 而且 $p \nmid (a, b, c)$. 故现可设 (2) 中 $p \nmid (a, b, c)$. 分如下情形。

(i) 若 $p\mid a, p\mid b, p \nmid c$, 则 (3) 为 $c \equiv 0\left(\mod  p\right)$, 无解。 从而 (2) 无解。

(ii) 若 $p \mid a, p \nmid b$, 则 (3) 为 $b x+c \equiv 0\left(\mod  p\right)$, 有解。 且 $f^{\prime}(x) \equiv b \equiv 0$ 无解。 故 (3) 的解可提升为 (2) 的解。 从而 (2) 有解。

(iii) 若 $p \nmid a, p>2$, 则 $\left(2 a, p^{s}\right)=1$, 即 2 和 $a$ 对模 $p^{s}$ 是可逆的。 可将 (2)式配方：
\end{frame}

\begin{frame}
  \color{gray}
\begin{align*}
4 a^{2} x^{2}+4 a b x+4 a c & \equiv 0 \quad\left(\mod  p^{s}\right) \\
(2 a x+b)^{2}-b^{2}+4 a c & \equiv 0 \quad\left(\mod  p^{s}\right) \\
y^{2} & \equiv \delta \quad\left(\mod  p^{s}\right) \tag{4}
\end{align*}
其中 $y \equiv 2 a x+b, \delta \equiv b^{2}-4 a c\left(\mod  p^{s}\right)$. 故 (2) 有解当且仅当 (4) 有解。 即化为 $\delta$是否二次剩余的问题。 当 (4) 有解时， 记其解为 $y \equiv \sqrt{\delta}$, 则 (2) 的解为
\[
x \equiv\left(-b \pm \sqrt{b^{2}-4 a c}\right) / 2 a \quad\left(\mod  p^{s}\right)
\]
(故中学时的求根公式实际上是有效的， $1 / a=a^{-1}$).

(iv) 若 $p=2$, $2 \nmid a$, 则 $f^{\prime}(x) \equiv 2 a x+b \equiv b\left(\mod  2\right)$.

(iv-1) 当 $2 \nmid b$ 时， $f^{\prime}(x) \equiv 0\left(\mod  2\right)$ 无解， 故 (2)归结为 (3), 而 (3) 现为 $x^{2}+x+c \equiv 0\left(\mod  2\right)$, 即 $c \equiv 0\left(\mod  2\right)$. 故 (2) 有解当且仅当 $2 \mid c$.

（iv-2）当 $2 \mid b$ 时，记 $b=2 b_{1}$. 因 $a$ 模 $2^{s}$ 可逆， (2) 式可配方：
\[
  \begin{aligned}
  a^{2} x^{2}+2 a b_{1} x+a c & \equiv 0 \quad\left(\mod  2^{s}\right) \\
\left(a x+b_{1}\right)^{2}-\left(b_{1}^{2}-a c\right) &\equiv 0 \quad\left(\mod  2^{s}\right) \\
y^{2}-\delta_{1} &\equiv 0 \quad\left(\mod  2^{s}\right)
\end{aligned}
\]
其中 $y=a x+b_{1}, \delta_{1}=b_{1}^{2}-a c$. 故 (2) 式有解当且仅当 $\delta_{1}$ 为二次剩余 (模 $2^{s}$).

\end{frame}

\begin{frame}
总之可知， 二次同余式的求解问题可归结为模 $p^{s}$ 或 $2^{s}$ 的二次剩余问题， 在 \S4.1 引理 1 和定理 1 , 以及以上各节已有深入结果。


\begin{comment*}%评述
Euler在 1745 年左右， 两次猜出二次互反律。 Legendre 在 1785 年证明过部分情况。 第一个完全的证明， 是 Gauss 给出， 其日记记为在 1796 年 4 月 8 日。 他后来共给出 8 个证明， 称之为黄金定律、基本定理、数论之宝。 许多数学家都投人研究， 现已知发表的证明有 200 多个， 进而有到各方面的发展推广， 特别是发展到高次互反律， 发展到代数整数， 发展到类域论， 发展到多项式。 我们将在附录 5 中介绍三次、四次互反律。 论数者赞这“互反律之妙”曰：
\begin{poem}
乾坤颠倒反掌间，有似漓江三月天。\\
水下分明天上月， 天上碧水飘白帆。
\end{poem}
\end{comment*}
\end{frame}

